#include <iostream>
#include <stack>
#include <queue>
using namespace std;

struct node
{
	int val;
	node *left;
	node *right;
	
	node(int v=0, node *l=NULL, node *r=NULL)
	{
		val = v;
		left = l;
		right = r;
	}
};

void preorder(node *root)
{
	if(root)
	{
		cout << root->val << " ";
		preorder(root->left);
		preorder(root->right);
	}
}

void preorder2(node *root)
{
	stack<node*> S;
	node* p = root;
	while(p || !S.empty())
	{
		if(p)
		{
			cout << p->val << " ";
			S.push(p);
			p = p->left;
		}
		else
		{
			p = S.top()->right;
			S.pop();
		}
	}
}

void inorder(node *root)
{
	if(root)
	{
		inorder(root->left);
		cout << root->val << " ";
		inorder(root->right);
	}
}

void inorder2(node *root)
{
	stack<node*> S;
	node *p = root;
	while(p || !S.empty())
	{
		if(p)
		{
			S.push(p);
			p = p->left;
		}
		else
		{
			cout << S.top()->val << " ";
			p = S.top()->right;
			S.pop();	
		}
	}
}


void postorder(node *root)
{
	if(root)
	{
		postorder(root->left);
		postorder(root->right);
		cout << root->val << " "; 
	}
}

void postorder2(node *root)
{
	stack<node*> S;
	node *p = root;
	while(p || !S.empty())
	{
		if(p)
		{
			S.push(p);
			S.push(NULL);
			p = p->left;
		}
		else
		{
			if(S.top() == NULL)
			{
				S.pop();
				p = S.top()->right;
			}
			else
			{
				cout << S.top()->val << " ";
				S.pop();
			}
		}
	}
}


void levelorder(node *root)
{
	queue<node*> Q;
	if(root)
		Q.push(root);
	while(!Q.empty())
	{
		node *p = Q.front();
		Q.pop();
		cout << p->val << " ";
		if(p->left)
			Q.push(p->left);
		if(p->right)
			Q.push(p->right);
	}
}

int main()
{
	node n4(4);
	node n5(5);
	node n6(6);
	node n2(2, &n4, &n5);
	node n3(3, NULL, &n6);
	node n1(1, &n2, &n3);
	cout << "===============preorder====================\n";
	preorder(&n1);
	cout<<endl;
	preorder2(&n1);
	cout<<endl;
	cout << "===============inorder====================\n";
	inorder(&n1);
	cout<<endl;
	inorder2(&n1);
	cout<<endl;
	cout << "===============postorder====================\n";
	postorder(&n1);
	cout<<endl;
	postorder2(&n1);
	cout<<endl;
	cout << "===============levelorder====================\n";
	levelorder(&n1);
	cout<<endl;
	return 0;
}
